Global Navigation Satellite Systems are systems allowing a receiver, located anywhere on or in the vicinity of the Earth, to compute its position by means of the signals broadcasted by synchronized satellite emitters. Examples of such systems are the Global Positioning System (GPS) [Kaplan, 1996], Glonass and Galileo [Hein, 2000]. A GNSS comprises a plurality of satellite emitters generating direct-sequence code-modulated signals [Utlaut, 1978], i.e. the code (taking values +1 and −1, or any other discrete set of values) multiplies the original signal. Therefore, a GNSS positioning signal is generally constituted by a superposition of individual code-modulated signals generated by a subset of said satellite emitters, each individual signal being defined by a known spreading code, by an unknown code delay and by an unknown carrier frequency shift (usually called “Doppler shift”, even if it is not entirely due to Doppler effect, but also to clock and oscillator frequency offsets). Determination of the code delay is the key to positioning, but a good “Doppler” frequency shift estimation is essential in order to perform an accurate code delay estimation [Kaplan, 1996, Tsui, 2005].
In GNSS systems, the positioning of a receiving unit first requires the estimation of the time of transmission and the time of reception of the signals coming from different satellite emitters. From the time of reception and the time of transmission the so-called pseudoranges between the receiver and each transmitter are computed. Then, the position is computed by triangulation using the pseudoranges and the position of the satellite emitters.
In the conventional usage of GNSS receivers, both the time of transmission and the position of the satellite emitter are obtained by estimating the code delay, i.e. the delay between the code of the incoming signal and a receivers' local replica of the code, synchronizing that local replica to the incoming signal code, and demodulating the information (also known as navigation message) carried on the incoming signal. Therefore, the code delay estimation for each signal coming from a satellite emitter will be one of the main tasks of the receiver. The pseudoranges are corrected before triangulation in order to remove errors coming from the satellite emitter clock, the satellite emitter movement (relativistic effects), and the propagation across the ionosphere and troposphere. The corrections for the first three errors can be obtained from the navigation message. For the last one, the receiver can apply some well-known models [Kaplan, 1996]. As the time reference used in the receiver is not synchronized to the one used by the transmitter, the receiver clock error is another unknown to be estimated, besides the three position coordinates. Therefore, at least the pseudoranges to four satellite emitters are required to fix the receiver position. If the receiver unit clock error is kept equal to zero by any means and/or some of the position coordinates are known, the number of required satellite emitters will be reduced by the number of unknowns that are eliminated.
In some occasions, it is not possible to demodulate the navigation message, either due to low level of the received signal or due to time constraints in the time to first fix (note that it would be required to obtain the information in the navigation message of each satellite emitter during a time interval up to thirty seconds). In that case, an assisted approach is used: the information contained in the navigation message is provided by a Location Server, which obtains the information from an outdoor receiver unit located nearby or from other means. This approach is denoted Assisted GNSS, A-GNSS in short (Assisted GPS or A-GPS for the particular case of GPS) and can reduce the time to first fix down to several seconds and can help reduce the minimum power required in the received signal. In the expected conditions of use of Assisted-GNSS, the navigation message is not generally retrieved and, hence, the receiver does not have available the “marks” on the signal indicating the time of transmission (such as, e.g., the time-of-the-week, TOW). The differences between times of transmission of the signals of the received satellite emitters can be determined directly from the measurements, but not the absolute value since there exist a constant but unknown term affecting all of them. This difficulty can be addressed in two ways:                Making measurements to at least five satellite emitters (instead of four, like in the conventional operation) and estimating that term in the process of fixing the receiver position [Peterson, 1995, Syrjarinne, 2000].        Synchronizing the receiver to the GNSS time reference with high accuracy. This allows the receiving unit to measure the transmission times without having access to the marks on the signals. As in the conventional operation, the minimum number of received satellite emitters is four. The tight synchronization can be attained by external means, such as the communications link between the Location Server and the receiver [3GPP, 2005].        
As suggested in the former paragraphs the position computation can take place in the receiver. This approach is normally named “receiver-based location calculation”. Nevertheless, for the sake of complexity and cost saving in the receiver, this computation could be performed in an external unit to which the receiver sends the signals' times of reception and pseudoranges, and other pertinent information via a data link. This approach is normally named “receiver-assisted location calculation” and was exploited by the U.S. Pat. No. 5,225,842 issued to Brown et al. The computation of the position could be done either in a conventional or in an assisted way depending on the data provided by the receiver and, eventually, by the Location Server.
Conventional GNSS signal processing and positioning algorithms fail when the receiver is located in highly-dense urban areas, such as urban canyons, or inside buildings. In both types of environments, GNSS signals are subject to high attenuation and blockage (due to propagation through buildings and so-called “urban canyons”), the so-called “near-far problem” (since signals coming from different satellite emitters experiment very different attenuation), and severe multipath due to signal reflection and diffraction [Lachapelle, 2004b]. Since the propagation in both types of environments, namely urban canyons and inside buildings, suffers from the same problems, they are hereafter jointly referred to as indoor environments.
Attenuation due to propagation in “indoor” environments can be more than 30 dB. Thus signals transmitted by the transmitting units on board the satellite emitters will reach an indoors receiver with a very weak level of power, given that GNSS are nominally designed for outdoors operation. This means that a high-sensitivity receiver is required to detect the signals; otherwise there will be no means to estimate their pseudoranges.
The fact that signals from different satellite emitters can experiment different attenuation as they follow different propagation paths gives rise to the so-called near-far problem: if two signals, coming from different transmitters, reach the receiver with a big difference in power, the code delay estimation of the weakest signal will present important errors due to the interference of the strongest one. This effect is called “near-far” in reference to the differences in received signal power experienced in cellular communication systems. In these systems, the power differences are due to the differences in distance from the mobile to the base stations; however, in GNSS the power differences are caused by the different attenuation of the propagation paths, and not by the differences in distance from the receiving unit to the satellites, which are relatively small. Near-far problem will not only affect the code delay estimate, but also the estimation of other parameters of the weakest signals, such as the frequency and the data (in case that it is possible to estimate the data). The error in the code delay can be very important and gives rise to high positioning errors. In an extreme case, the weakest signal could not even be detected by the receiving unit. In direct sequence modulated systems, the difference in power between received signals that is tolerated by the receiver without suffering from the near-far problem depends on the cross-correlation of the codes modulating the signals. In GNSS-based positioning, the near-far problem does not appear outdoors (i.e. open field), since all the signals arrive at the receiver with nearly the same power.
Multipath refers to the fact that the receiver can receive several signals coming from the same transmitter that have propagated along different paths. This problem also happens outdoors, where there is a line-of-sight signal (also called direct-ray signal), which is the one to be used in the pseudorange estimation, and other delayed replicas of the signal with smaller amplitude that are originated by reflection and/or diffraction on obstacles around the receiver. The delayed replicas cause an additional error in the code delay estimation of the desired signal, which is the line-of-sight signal, if it exists, or otherwise the signal with the shortest propagation path. This error is ultimately due to the fact that the receiver cannot distinguish the desired signal from the rest when their relative delays are small compared to the inverse of the signal bandwidth. The multipath effect is much more significant indoors, since the building structure and the number of objects surrounding the receiver facilitates the appearance of reflections and diffractions.
Given the above-referred problems, conventional GNSS receivers, designed for outdoor applications, are not able to work properly indoors since they fail in accurately estimating the code delay of the signal generated by the individual satellite emitters. Lack of an accurate estimation of the code delay forbids accurate positioning of the receiver unit.
Some of the difficulties associated with indoor positioning are well known, and several solutions have been proposed in the past, none of which gives complete satisfaction.
Many outdoor GNSS receivers are based on the so-called “acquisition and tracking” architecture, comprising two stages. In the first “acquisition” stage a coarse estimation of both code delay and carrier frequency shift is computed. These estimations are refined in the “tracking” stage. This technique will be described in detail with reference to FIGS. 1A, 1B and 2.
The former architecture has been the baseline for several patents dealing with positioning using weak code modulated signals, such as the U.S. Pat. No. 6,707,423 issued to Turetzky et al, and the U.S. Pat. No. 6,795,771 issued to Fuchs et al. The adaptation of this structure to weak signals has been also treated in the literature [Lachapelle, 2004a, Lopez-Risueno, 2004, Psiaki, 2001], often under the name of High Sensitivity GPS or High Sensitivity GNSS receiver. Mainly, the processing of weak signals requires the use of both long coherent correlation times and large noncoherent integration during acquisition (see FIG. 1A), and the use of narrowband loops during tracking. For instance, for GPS L1 C/A signals, coherent correlation could be on the order of 10 ms per block or greater, and the noncoherent integration could extend beyond 100 blocks, so that the overall dwell time would be on the order of seconds.
The large dwell time required for low acquisition threshold leads to complex acquisition stages and large acquisition times. Thus, assisted information coming form a Location Server nearby is used in references above, i.e. they work in Assisted-GNSS mode rather than in standalone mode. The required assisted information is at least the list of visible transmitters in the area, i.e. the in-view satellite emitters, and their approximate Doppler frequencies. This way, the acquisition narrows the delay-Doppler search and can be accomplished in an affordable way: They perform acquisition based on the FFT (see FIG. 1B) but searching a few Doppler frequencies only. Nevertheless, the main problem of those approaches is the use of tracking, since it makes the receiver work continuously. This is a major problem concerning power consumption because these kinds of receivers are intended to be mounted on a mobile platform, like a mobile phone.
The use of receivers with only acquisition allows working with snapshots of the signal instead of digitalizing samples continuously. However, it raises the problem of the poor estimation of the code delay in the acquisition stage. In several embodiments, the U.S. Pat. No. 5,663,734, issued to Krasner, describes receiving units working with signal snapshots and comprising only acquisition via the FFT (see FIG. 1B). To improve the code delay estimation a further interpolation using the correlation samples around the correlation peak is performed. The embodiments of that patent also work in Assisted-GNSS mode to facilitate the acquisition. The drawback of those embodiments is that they work properly only when i) the code period is a multiple of the sampling period and ii) for moderately-long dwell times, i.e. on the order of 1 second or less. If i) is not complied, the FFT-based acquisition leads to an error in the code delay estimation, despite the use of interpolation. Due to technical constraints, it is not always possible to select a sampling frequency fulfilling the former condition. Regarding long dwell times, i.e. larger than 1 second, even small differences between the trial Doppler frequencies and the real one can lead to a degradation in the correlation computation due to the Doppler effect in the code and, subsequently, to an error in the code delay estimation. Long dwell times of several seconds will be required for indoor environments.
On the other hand, the U.S. Pat. No. 6,795,771, issued to Fuchs et al, includes one embodiment with only acquisition, which uses the FFT-based acquisition, selects a peak and performs conventional correlations for several delays around the peak. However, in order to obtain an integer number of samples per code period, re-sampling of the incoming signal is performed at the expense of increasing the receiver complexity. Nevertheless, the problem of long dwell times is neither dealt with nor solved.
Regarding the near-far problem, also known as cross-correlation mitigation, several methods to detect it have been proposed in previous patents (U.S. Pat. No. 6,236,354 issued to Krasner, U.S. Pat. No. 6,795,771 issued to Fuchs et al, U.S. Pat. No. 6,646,596 issued to Syrjarinne et al, U.S. Pat. No. 6,707,423 issued to Tureztky et al), patent applications (US Patent Application No. 20050099334 issued to Roh) and literature [Glennon, 2004]. First, they try to detect whether or not the correlation between an incoming signal and its replica is affected by the interference of a stronger signal coming from a different transmitting unit mainly by looking for the strongest satellite emitter signals and computing the difference in power between strong and weak signals. If the interference of a stronger signal is detected, while some techniques simply do not consider the weaker signal for positioning purposes, others try to mitigate the cross-correlation by looking for the right correlation peak among all the peaks coming from the afore-mentioned interference. Further, the U.S. Pat. No. 6,236,354 issued to Krasner tries to remove the interference either by estimating and removing the strongest signal before correlation, or by, less-effectively, estimating and removing its contribution to the cross-correlation after correlation. The removal of the strongest signal is also known in the literature as successive interference cancellation [Madhani, 2003].
In order to understand the limitations of the previous methods, it is worth noting that once a satellite emitter signal has been acquired, if the delay was correctly estimated (i.e. it was not erroneous due to near-far problem), the receiver clock frequency error can be determined, and hence the Doppler search for the rest of the remaining satellite emitters can be reduced. Furthermore, a rough estimate of the difference in delay of the remaining satellite emitters can be provided by the Location Server. This difference in delay refers to the difference between the delay of the acquired satellite emitter and the delay of the remaining satellite emitters. In so doing, the acquisition of the remaining satellite emitters could be further simplified, and only the exploration of a few delay-Doppler pairs would be necessary.
A main problem with the previous methods is that they require that either all the satellite emitters or at least the strong ones (the ones received with higher power level, which are likely to produce interferences) have been acquired before running the near-far problem detection and/or mitigation algorithm. This increases the processing time. Further, a reduced delay-Doppler space after the first satellite emitter acquisition cannot be performed since it is not assured that this first satellite emitter is unaffected by the near-far problem.